using Xunit;
using System;
using System.Collections.Generic;
using Newtonsoft.Json;

namespace LeetCodeQuestionBank.Algorithm
{
    public class No0088_Merge
    {
        /*
        给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
        初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
        你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。
        示例 1：
            输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
            输出：[1,2,2,3,5,6]

        示例 2：
            输入：nums1 = [1], m = 1, nums2 = [], n = 0
            输出：[1]
        提示：
            nums1.length == m + n
            nums2.length == n
            0 <= m, n <= 200
            1 <= m + n <= 200
            -10^9 <= nums1[i], nums2[i] <= 10^9
        */
        public static IEnumerable<object[]> GetTestArgs()
        {
            return new object[][] {
                new object[] {
                    "[1,2,3,0,0,0]", 3, "[2,5,6]", 3,
                    "[1,2,2,3,5,6]",
                },
                new object[] {
                    "[1]", 1, "[]", 0,
                    "[1]",
                },
            };
        }

        [Theory]
        [MemberData(nameof(GetTestArgs))]
        public void Test_Merge(string nums1_json, int m, string nums2_json, int n, string result_json)
        {
            int[] nums1 = JsonConvert.DeserializeObject<int[]>(nums1_json);
            int[] nums2 = JsonConvert.DeserializeObject<int[]>(nums2_json);
            int[] result = JsonConvert.DeserializeObject<int[]>(result_json);

            Merge(nums1, m, nums2, n);
            Assert.Equal(result, nums1);
        }

        private void Merge(int[] nums1, int m, int[] nums2, int n)
        {
            int[] temp = new int[nums1.Length];
            int i = 0, j = 0;
            int k = 0;
            while (i < m && j < n)
            {
                temp[k++] = nums1[i] <= nums2[j] ? nums1[i++] : nums2[j++];
            }
            while (i < m) temp[k++] = nums1[i++];
            while (j < n) temp[k++] = nums2[j++];
            for (int p = 0; p < temp.Length; p++)
                nums1[p] = temp[p];
        }
    }
}
